Nowadays, structured documents are widely used, in particular on the World Wide Web.
HTML, SVG (standing for “Scalable Vector Graphics”) and XML are examples of markup language used to create such structured documents.
The XML format is a syntax for defining computer languages, which makes it possible to create languages adapted to different uses which may however be processed by the same tools.
An XML document is composed of elements, each element being delimited by an opening tag (or start tag) comprising the name of the element (for example: <tag>) and a closing tag (or end tag) which also comprises the name of the element (for example </tag>). Each element may contain other elements in a hierarchical child-parent relationship and/or contain text data or value defining content. Given these structure tags, data in such a document is referred to as “structured data”.
The definition of an element may also be refined by a set of attributes, each attribute being defined by a name and having a value. The attributes are then placed in the start tag of the element they are refining (for example <tag attribute=“value”>).
XML syntax also makes it possible to define comments (for example: “<!—Comment—>”) and processing instructions, which may specify to a computer application what processing operations to apply to the XML document (for example: “<?myprocessing?>”).
Several different languages based on the XML language may contain elements of the same name. To be able to mix several different languages, an addition has been made to XML syntax making it possible to define “Namespaces”. Two elements are identical only if they have the same name and are situated in the same namespace. These two elements are then said to have the same “qualified name”.
In XML terminology, the set of the terms “element”, “attribute”, “text data”, “comment” and “processing instruction” are grouped together under the generic name of “item”.
XML items, and more generally structured items, comprise two kinds of information: on the one hand, structure information which includes information defining the structure of the items, for example opening and closing tags or the attribute names; and on the other hand, content information or “value” corresponding to the value taken by the items, for example the value of an attribute or the text data of an element.
To process an XML document, it must be read into memory. However, more than one reading approach exist.
A first family of reading approaches consists in reading the XML document as a sequence of events, processing one event at a time.
Each XML item is described in terms of events, namely XML events. Some events only refer to structure information of the item, for example the opening tag, the closing tag, a comment tag, etc. Other events only refer to content information of the item, for example an attribute value or text data.
The methods of this family, such as for example the SAX API (standing for “Simple API for XML”), allow the XML document to be read by streaming, enabling use of little memory space. However, easy access to any desired part of the data is not provided by these approaches.
A second family of reading approaches consists in representing all the structured data of the XML document in memory as a hierarchical tree-like data structure. An example of such structure, also referred to as “tree structure” or “tree data structure” or “tree” in the following description, is the DOM tree (standing for “Document Object Model”).
The methods of this family generally enable easy and fast access to each part of the XML document. However, they require a large amount of memory to store all the structured data simultaneously.
The DOM format is a set of specifications of the W3C describing a model for representing XML data in the form of a tree. The tree is generally formed from nodes to which elements of the document correspond, the hierarchy of the nodes being in accordance with the hierarchy of the elements within the XML document. This hierarchy defines the concept of parent node/element—child node/element.
Each node moreover possesses a set of properties making it possible to store in memory for example the attributes relative to the corresponding XML element of the node or to provide functionalities specific to the DOM specification via libraries of functions. Thus, several XML events may be grouped together in the same DOM node (for example the start element event and the events relative to all the attributes of that element). An example of structuring of the nodes is documented in the DOM recommendation.
Contrary to the model for processing by stream (StAX or SAX) in which the data are presented event by event, the structured data of an XML document are, in the DOM interface, entirely placed in memory in the DOM tree. The API interfaces of DOM type thus make it possible to rapidly access any element of structured data.
In accordance with the DOM recommendation, the representation in DOM tree form gives numerous functionalities for paths or for manipulation of the nodes of the tree, such as:                each element may directly access all its direct children and all its attributes;        a function enables access to all the elements having the same qualified name;        a function, known by the name of “mutation event”, gives notification of the modifications of a DOM tree. Such modifications of tree nodes are thus easily identified. These mutation events make it possible to call functions on modifying the DOM tree, in particular the insertion or the deletion of an element, an attribute or a text node; or the modification of the value of an attribute or of a text node.        
To overcome the main drawback of XML syntax which is to be verbose, methods of compressing and encoding an XML document exist, resulting in compressed documents having a reduced size.
This is in particular the case for the Binary XML formats that produce binary bitstream.
Advanced mechanisms, such as some involved in EXI and Fast Infoset Binary formats, use indexing tables (for example grammars) to represent the structure information into a compact way and also use specific codecs and indexation techniques to encode efficiently the content or values of the structured data.
While the structured data is generally encoded linearly, EXI provides two specific compression modes that rearrange the values within the EXI bitstream before encoding, so that similar values are stored next to the other: a mode referred to as “pre-compression” and a mode referred to as “compression”, which distinguish from each other by the additional implementation for the “compression” mode of a final lossless compression algorithm (DEFLATE).
Rearrangement of the values reduces entropy of the data by grouping together similar information, and thus better compression of the XML data is obtained.
This involves:                grouping the XML event structure information, while keeping the original order of the original structured data, to obtain a structure channel,        grouping the XML event content information (values, names, etc.) relating to the same structure information (i.e. having the same qualified name [qname], such as the same element name or attribute name) to obtain a respective plurality of value channels. In each value channel, the values are kept in the original order of the values in the original structured data,        putting the value channels in order according to the corresponding structure information (i.e. the structure channel), that is to say in the order of the first occurrences in the original XML data of the associated qualified names,        encoding the structure channel and then the value channels in the resulting order. The values are encoded one after the other in each value channel, and the value channels are encoded one after the other. For each value channel, a local indexing table is used to index the values, possibly taking into account a type of the values (i.e. integer, float, string, etc.).        
The HTML format relies on a restricted number of possible structural elements (structural semantics), defined in a standard.
HTML is used by web authors to define visual structure for content on the World Wide Web. The end user is presented with this content by viewing the content on a computer display, after the content has been rendered into a visual format by a web browser based on the HTML visual structure.
The values of the HTML elements are the content to render, while the values of the attributes may specify the rendering style, i.e. how this content has to be rendered and displayed (color, font, etc.).
HTML elements of a web page, originally defined in a static manner, now make reference to embedded scripts in languages such as Javascript which dynamically affect the behaviour of the web pages and then the rendering thereof. For example, based on the movement of the mouse in a web browser, the content of a web page may change.
Web browsers can also refer to Cascading Style Sheets (CSS) to define the appearance and layout of the content to render.
CSS define properties that are attached to categories of markup elements defined through CSS selectors and which guide the rendering of those elements.
CSS selectors select elements through different means, in particular based on the element name, element-specific attributes, like class or id or the parent element name.
A first CSS exemplary rule “h1{color:#00ff00}” matches against all ‘h1’ markup elements of the web page, for which it sets the text color property to green.
A second CSS exemplary rule “p.ex {color:#0000ff; margin-bottom:100px;}” matches against all ‘p’ markup elements that have the class attribute value equal to ‘ex’. This rule sets the text color of those selected elements to blue and their bottom margin to 100 pixels.
An example of conventional processing by a web browser is illustrated in FIG. 1a, which shows a processor 1.
HTML data or any structured data 10 is input to a parser 12 which produces tokens, for example elements, items or events. All the parsed tokens are used by a DOM building unit 14 to generate a DOM tree in memory. The resulting DOM tree “DTree” strictly matches the structured data 10, in that it stores all the structured data of each parsed token, keeping the original structure.
Next, a render tree building unit 18 generates a render tree “RTree” from the DOM tree in memory and style sheets 16. Only the content of DOM nodes that have to be rendered are comprised in the render tree, taking into account the associated styles defined in the style sheets 16.
It is to be noted that generally the CSS selectors match to the DOM representation, providing an efficient attachment of CSS properties to the corresponding HTML elements.
A draw and display engine 20 then produces the rendering of the HML data on a display device, based on the render tree RTree.
The DOM tree DTree is used to store the HTML data to allow interactivity and dynamic behaviour of this HTML data in response to inputs from a user interacting with the displayed HTML data or to any network inputs. Since the DOM tree provides programmatic access functions (e.g. the above mentioned functionalities for path and for DOM tree manipulation), scripts such as Javascript can efficiently modify the HTML data within the DOM tree in response to the user or network inputs.
Modification of the DOM tree may comprise adding, removing, updating, moving, animating or hiding DOM nodes.
Each time the DOM tree is modified such that the rendering of the HTML data is also modified (i.e. the document content to render changes), the render tree RTree is correspondingly modified. To achieve this, it is provided for the render tree to be synchronized with the DOM tree.
FIG. 1b illustrates improved processing to render structured data. Parsing, DOM tree building and render tree building are parallelized (see branches 12-14-18, 12a-14a-18a and 12b-14b-18b). In particular, this is efficiently implemented in multi-core architectures wherein each core may process a single piece of the HTML data to render.
The HTML data 10 is split into several pieces, each piece being parsed in one of the parallelized branches to generate a partial DOM tree (not shown) and a partial render tree (not shown) in a similar manner to that described above with reference to FIG. 1a. 
Once every piece of the HTML data 10 has been processed, a tree aggregator 19 is used to aggregate all the partial DOM trees into the DOM tree DTree representing the entire HTML data 10. Similarly, all the partial render trees are aggregated into the render tree RTree representing the content to render of the entire HTML data 10, taking into account the style sheets 16.
The draw and display engine 20 uses the RTree tree to render the HTML data content on the display device.
For example, the publication “Parallelizing the Web Browser”, available at the web location http://usenix.org/events/hotpar09/tech/full_papers/jones/jones_html/, discusses parallelization for web page rendering.
When the structured data (HTML, XML, SVG, etc.) are provided in a compressed form (e.g. EXI), a third tree may be built when decompressing the data in order to build the DOM tree DTree, for example to store the structure channel and value channels of an EXI bitstream with compression mode, or the value types before obtaining the values.
Handling the two or three tree structures as described above requires a lot of computation and a significant amount of memory. The impact on computation and memory use is particularly high when processing complex structured data (complex web pages) or when the processor is part of a handheld device with limited resources. In particular, it may drain the battery of such a handheld device, or may cause slow display of the structured data.
It would therefore be desirable to improve the processing of structured data to render, with the aim of reducing the processing costs and possibly improving the rendering.